home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-pppext-stacker-00.txt < prev    next >
Text File  |  1993-10-20  |  12KB  |  551 lines
  1.  
  2. Network Working Group                                        Robert Lutz
  3. Internet Draft                                          Stac Electronics
  4. expires in six months                                       October 1993
  5.  
  6.  
  7.                   PPP Stacker LZS Compression Protocol
  8.                     draft-ietf-pppext-stacker-00.txt
  9.  
  10.  
  11.  
  12. Status of this Memo
  13.  
  14.    This document is the product of the Point-to-Point Protocol Working
  15.    Group of the Internet Engineering Task Force (IETF).  Comments should
  16.    be submitted to the ietf-ppp@ucdavis.edu mailing list.
  17.  
  18.    Distribution of this memo is unlimited.
  19.  
  20.    This document is an Internet Draft.  Internet Drafts are working
  21.    documents of the Internet Engineering Task Force (IETF), its Areas,
  22.    and its Working Groups.  Note that other groups may also distribute
  23.    working documents as Internet Drafts.
  24.  
  25.    Internet Drafts are draft documents valid for a maximum of six
  26.    months.  Internet Drafts may be updated, replaced, or obsoleted by
  27.    other documents at any time.  It is not appropriate to use Internet
  28.    Drafts as reference material or to cite them other than as a
  29.    ``working draft'' or ``work in progress.''
  30.  
  31.    Please check the 1id-abstracts.txt listing contained in the
  32.    internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net,
  33.    nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the
  34.    current status of any Internet Draft.
  35.  
  36.  
  37. Abstract
  38.  
  39.    The Point-to-Point Protocol (PPP) [1] provides a standard method for
  40.    transporting multi-protocol datagrams over point-to-point links.
  41.  
  42.    The PPP Compression Control Protocol [2] provides a method to
  43.    negotiate and utilize compression protocols over PPP encapsulated
  44.    links.
  45.  
  46.    This document describes the use of the Stacker LZS data compression
  47.    algorithm, with single or multiple compression histories, for
  48.    compressing PPP encapsulated packets.
  49.  
  50.  
  51.  
  52.  
  53. Lutz                     expires in six months                  [Page i]
  54. DRAFT                         Stacker LZS                   October 1993
  55.  
  56.  
  57. 1.  Introduction
  58.  
  59.    Starting with a sliding window compression history, similar to LZ1
  60.    [3], Stac Electronics developed a new, enhanced compression algorithm
  61.    identified as Stacker LZS.  The LZS algorithm is optimized to
  62.    compress all file types as efficiently as possible.  Even string
  63.    matches as short as two bytes are effectively compressed.
  64.  
  65.    The Stacker LZS compression algorithm supports both single
  66.    compression history communication and multiple compression history
  67.    communication.
  68.  
  69.    A single compression history will require the minimum amount of
  70.    memory to implement, but may not provide as much compression as a
  71.    multiple history implementation.
  72.  
  73.    Using multiple compression histories can improve the compression
  74.    ratio of a communication link by associating separate compression
  75.    histories with separate virtual links of communication.  In general,
  76.    each virtual link will transmit data that is independent of other
  77.    virtual links.
  78.  
  79.  
  80. 1.1.  Licensing
  81.  
  82.    Source and object licenses are available on a non-discriminatory
  83.    basis for either a royalty or fixed price arrangement.  Hardware
  84.    implementations are also available.  Patent indemnity is included
  85.    with the license.
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108. Lutz                     expires in six months                  [Page 1]
  109. DRAFT                         Stacker LZS                   October 1993
  110.  
  111.  
  112. 2.  LZS Packets
  113.  
  114.    Before any LZS packets may be communicated, PPP must reach the
  115.    Network-Layer Protocol phase, and the CCP Control Protocol must reach
  116.    the Opened state.
  117.  
  118.    Exactly one LZS datagram is encapsulated in the PPP Information
  119.    field, where the PPP Protocol field indicates type hex 00FD
  120.    (compressed datagram).
  121.  
  122.    The maximum length of the LZS datagram transmitted over a PPP link is
  123.    the same as the maximum length of the Information field of a PPP
  124.    encapsulated packet.
  125.  
  126.    Prior to compression, the uncompressed data begins with the PPP
  127.    Protocol number.  This value MAY be compressed when Protocol-Field-
  128.    Compression is negotiated.
  129.  
  130.    PPP Link Control Protocol packets MUST NOT be sent within compressed
  131.    data.
  132.  
  133.    Padding
  134.  
  135.       The LZS Information field contains an integral length field, which
  136.       is used to disambiguate padding.  When expansion has resulted in
  137.       the number of octets specified in the length, the remainder of the
  138.       packet is considered padding.  This allows trailing bits as well
  139.       as octets to be considered padding.
  140.  
  141.    Reliability and Sequencing
  142.  
  143.       By default, the Compression History will be reset for each LZS
  144.       packet.  In this case, the algorithm does not depend on a reliable
  145.       link and does not require that packets be delivered in sequence.
  146.  
  147.       Optionally, each Compression History may be reset at the
  148.       discretion of the transmitter.  Use of this feature requires a
  149.       reliable link, as described in "PPP Reliable Transmission" [4],
  150.       and expects the packets to be delivered in sequence.
  151.  
  152.       When a transmitter resets a Compression History, no other
  153.       indication needs to be sent to the receiver, other than that
  154.       provided within the compressed information.
  155.  
  156.    Data Expansion
  157.  
  158.       The maximum expansion of Stacker LZS is 12.5%.
  159.  
  160.  
  161.  
  162.  
  163. Lutz                     expires in six months                  [Page 2]
  164. DRAFT                         Stacker LZS                   October 1993
  165.  
  166.  
  167.       When the expansion exceeds the size of the peer's Maximum Receive
  168.       Unit for the link, the expanded packet is sent in multiple PPP
  169.       frames.  When such frames are delivered out of sequence, the
  170.       parity check in each frame will detect the failure.
  171.  
  172.       When expansion is detected, the PPP packet MAY be sent without
  173.       compression.  Any following LZS packet will indicate a reset of
  174.       its Compression History.
  175.  
  176.  
  177. 2.1.  Packet Format
  178.  
  179.    A summary of the Stacker LZS packet format is shown below.  The
  180.    fields are transmitted from left to right.
  181.  
  182.     0                   1                   2                   3
  183.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  184.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  185.    |         PPP Protocol          |         History Number        |
  186.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  187.    |     Uncompressed Length       |     Compressed Data ...
  188.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  189.    |      LCB      /      CRC      |
  190.    +-+-+-+-+-+-+-+-+- - - - - - - -+
  191.  
  192.  
  193.    PPP Protocol
  194.  
  195.       The PPP Protocol field is described in the Point-to-Point Protocol
  196.       Encapsulation [1].
  197.  
  198.       When the Stacker LZS compression protocol is successfully
  199.       negotiated by the PPP Compression Control Protocol [2], the value
  200.       is 00fd hex.  This value MAY be compressed when Protocol-Field-
  201.       Compression is negotiated.
  202.  
  203.    History Number
  204.  
  205.       The number of the compression history which should be used.  This
  206.       field is only present when the negotiated History Count is greater
  207.       than one.
  208.  
  209.       If the negotiated History Count is one, this field is removed, a
  210.       reduction of 2 octets.
  211.  
  212.    Uncompressed Length
  213.  
  214.       The number of octets which were in the original PPP encapsulated
  215.  
  216.  
  217.  
  218. Lutz                     expires in six months                  [Page 3]
  219. DRAFT                         Stacker LZS                   October 1993
  220.  
  221.  
  222.       packet, prior to compression.
  223.  
  224.    Compressed Data
  225.  
  226.       The compressed PPP encapsulated packet.
  227.  
  228.    LCB or CRC
  229.  
  230.       By default, a simple Longitudinal Check Byte (LCB) will be
  231.       appended to each packet.  The LCB MUST be initialized to FF(hex)
  232.       at the beginning of each packet.  The LCB is one octet, and is the
  233.       Exclusive-OR of each octet of the original, uncompressed data.
  234.  
  235.       If the CRC option is successfully negotiated, a CRC will be
  236.       appended to each packet in place of the LCB.  The CRC MUST be
  237.       initialized to FFFF(hex) at the beginning of each packet.  The CRC
  238.       is two octets, and is based on the following polynomial:
  239.  
  240.          x^16 + x^12 + x^5 + 1
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273. Lutz                     expires in six months                  [Page 4]
  274. DRAFT                         Stacker LZS                   October 1993
  275.  
  276.  
  277. 3.  Configuration Option Format
  278.  
  279.  
  280.    Description
  281.  
  282.       The CCP Stacker-LZS Configuration Option negotiates the use of
  283.       Stacker LZS on the link.  By default or ultimate disagreement, no
  284.       compression is used.
  285.  
  286.    A summary of the Stacker-LZS Configuration Option format is shown
  287.    below.  The fields are transmitted from left to right.
  288.  
  289.     0                   1                   2                   3
  290.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  291.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  292.    |     Type      |    Length     |        History Count          |
  293.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  294.    |   Check Mode  |   Reset Mode  |
  295.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  296.  
  297.  
  298.    Type
  299.  
  300.       <TBD> (5)
  301.  
  302.    Length
  303.  
  304.       6
  305.  
  306.    History Count
  307.  
  308.       The History Count field is two octets, and specifies the maximum
  309.       number of Compression Histories.  Valid values range from 1 to
  310.       65768.
  311.  
  312.    Check Mode
  313.  
  314.       The Check Mode indicates support of LCB or CRC checking.  All
  315.       implementations MUST support LCB parity.
  316.  
  317.          1    LCB
  318.          2    CRC
  319.  
  320.  
  321.    Reset Mode
  322.  
  323.       The Reset Mode indicates support for maintaining a Compression
  324.       History for more than a single packet.  All implementations MUST
  325.  
  326.  
  327.  
  328. Lutz                     expires in six months                  [Page 5]
  329. DRAFT                         Stacker LZS                   October 1993
  330.  
  331.  
  332.       support the Single Packet mode.
  333.  
  334.          1    Single Packet
  335.          2    Multiple Packets
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383. Lutz                     expires in six months                  [Page 6]
  384. DRAFT                         Stacker LZS                   October 1993
  385.  
  386.  
  387. Security Considerations
  388.  
  389.    Security issues are not discussed in this memo.
  390.  
  391.  
  392. References
  393.  
  394.    [1]   Simpson, W.A., "The Point-to-Point Protocol (PPP)", work in
  395.          progress.
  396.  
  397.    [2]   Rand, D., "The PPP Compression Control Protocol (CCP)", work in
  398.          progress.
  399.  
  400.    [3]   Lempel, A. and Ziv, J., "A Universal Algorithm for Sequential
  401.          Data Compression", IEEE Transactions On Information Theory,
  402.          Vol. IT-23, No. 3, May 1977.
  403.  
  404.    [4]   Rand, D., "PPP Reliable Transmission", work in progress.
  405.  
  406.  
  407. Acknowledgments
  408.  
  409.    Editting and formatting by Bill Simpson.
  410.  
  411.  
  412.  
  413.  
  414.  
  415.  
  416.  
  417.  
  418.  
  419.  
  420.  
  421.  
  422.  
  423.  
  424.  
  425.  
  426.  
  427.  
  428.  
  429.  
  430.  
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438. Lutz                     expires in six months                  [Page 7]
  439. DRAFT                         Stacker LZS                   October 1993
  440.  
  441.  
  442. Chair's Address
  443.  
  444.    The working group can be contacted via the current chair:
  445.  
  446.       Fred Baker
  447.       Advanced Computer Communications
  448.       315 Bollay Drive
  449.       Santa Barbara, California  93117
  450.  
  451.       EMail: fbaker@acc.com
  452.  
  453.  
  454. Author's Address
  455.  
  456.    Questions about this memo can also be directed to:
  457.  
  458.       Robert Lutz
  459.       Stac Electronics
  460.       5993 Avenida Encinas
  461.       Carlsbad, CA  92008
  462.  
  463.       (619)431-7474
  464.  
  465.       Email: stac/stac/bobl%stac_electronics@mcimail.com
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493. Lutz                     expires in six months                  [Page 8]
  494. DRAFT                         Stacker LZS                   October 1993
  495.  
  496.  
  497.                            Table of Contents
  498.  
  499.  
  500.      1.     Introduction ..........................................    1
  501.         1.1       Licensing .......................................    1
  502.  
  503.      2.     LZS Packets ...........................................    2
  504.         2.1       Packet Format ...................................    3
  505.  
  506.      3.     Configuration Option Format ...........................    5
  507.  
  508.      SECURITY CONSIDERATIONS ......................................    7
  509.  
  510.      REFERENCES ...................................................    7
  511.  
  512.      ACKNOWLEDGEMENTS .............................................    7
  513.  
  514.      CHAIR'S ADDRESS ..............................................    8
  515.  
  516.      AUTHOR'S ADDRESS .............................................    8
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.  
  529.  
  530.  
  531.  
  532.  
  533.  
  534.  
  535.  
  536.  
  537.  
  538.  
  539.  
  540.  
  541.  
  542.  
  543.  
  544.  
  545.  
  546.  
  547.  
  548.  
  549.  
  550. Bill.Simpson@um.cc.umich.edu
  551.